//
// Created by sjjmw on 1/22/2022.
//

#ifndef LEETCODE__96_H
#define LEETCODE__96_H
#include "base.h"

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            //i=2 对应 2
            int final = 0;

            //2:0-1 3:0-2
            for (int j = 0; j < i; j++)
            {
                int q = i - j - 1;
                final += dp[j] * dp[q];
            }
            dp[i] = final;
        }
        return dp[n];
    }
};

int main()
{
    Solution().numTrees(3);
    return 0;
}
#endif //LEETCODE__96_H
